#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
    TreeNode *dfs(TreeNode *ancester, int &pval, int &qval)
    {
        if (ancester == NULL || pval == ancester->val || qval == ancester->val)
            return ancester;
        TreeNode *l = NULL, *r = NULL;
        l = dfs(ancester->left, pval, qval);
        r = dfs(ancester->right, pval, qval);
        if (l != NULL && r != NULL)
            return ancester;
        else
            return l != NULL ? l : r;
    }
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        return dfs(root, p->val, q->val);
    }
};